#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int n = nums.size(), ma = 0;
        unordered_map<int, int> hash;
        for (auto i : nums) hash[i]++, ma = max(ma, i);
        int df[10001] = { 0 }, dg[10001] = { 0 };
        for (int i = 1; i <= ma; i++) {
            df[i] = dg[i - 1] + hash[i] * i;
            dg[i] = max(dg[i - 1], df[i - 1]);
        }
        return max(df[ma], dg[ma]);
    }
};